{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# ModInt: a simple modular integer type"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "struct ModInt{n} <: Integer\n",
    "    k::Int\n",
    "\n",
    "    # Constructor definition...\n",
    "    # note the left side looks like the call it defines\n",
    "    ModInt{n}(k::Int) where {n} = new(mod(k,n))\n",
    "end"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a = ModInt{13}(1238279873492834)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b = ModInt{13}(9872349827349827)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a + b"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "To extend standard functions we need to import them."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Base: +"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "+(a::ModInt{n}, b::ModInt{n}) where {n} = ModInt{n}(a.k + b.k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a + b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "import Base: *, -\n",
    "\n",
    "*(a::ModInt{n}, b::ModInt{n}) where{n} = ModInt{n}(a.k * b.k)\n",
    "-(a::ModInt{n}, b::ModInt{n}) where {n} = ModInt{n}(a.k - b.k)\n",
    "-(a::ModInt{n}) where {n} = ModInt{n}(-a.k)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a * b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a - b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "-b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.show(io::IO, a::ModInt{n}) where {n} =\n",
    "    get(io, :compact, false) ? show(io, a.k) : print(io, \"$(a.k) mod $n\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "b"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.promote_rule(::Type{ModInt{n}}, ::Type{Int}) where {n} = ModInt{n}"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "Base.convert(::Type{ModInt{n}}, x::Int) where {n} = ModInt{n}(x)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "a + 1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "1 + a"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A = map(ModInt{13}, rand(1:100, 5, 5))"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "A^100000000"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "2A^100 .- 1"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Summary\n",
    "\n",
    "Here is all the code that defines the `ModInt` type:\n",
    "```jl\n",
    "struct ModInt{n} <: Integer\n",
    "    k::Int\n",
    "\n",
    "    # Constructor definition...\n",
    "    # note the left side looks like the call it defines\n",
    "    ModInt{n}(k::Int) where {n} = new(mod(k,n))\n",
    "end\n",
    "\n",
    "import Base: +, *, -\n",
    "\n",
    "+(a::ModInt{n}, b::ModInt{n}) where {n} = ModInt{n}(a.k + b.k)\n",
    "*(a::ModInt{n}, b::ModInt{n}) where{n} = ModInt{n}(a.k * b.k)\n",
    "-(a::ModInt{n}, b::ModInt{n}) where {n} = ModInt{n}(a.k - b.k)\n",
    "-(a::ModInt{n}) where {n} = ModInt{n}(-a.k)\n",
    "\n",
    "Base.show(io::IO, a::ModInt{n}) where {n} =\n",
    "    get(io, :compact, false) ? show(io, a.k) : print(io, \"$(a.k) mod $n\")\n",
    "\n",
    "Base.promote_rule(::Type{ModInt{n}}, ::Type{Int}) where {n} = ModInt{n}\n",
    "Base.convert(::Type{ModInt{n}}, x::Int) where {n} = ModInt{n}(x)\n",
    "```"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Exercise\n",
    "\n",
    "Add two methods that allows operations between modular integers with different modulus using the rule that they should combine in the modulus that is the `lcm` (least common multiple) of the moduli of the arguments.\n",
    "\n",
    "**Hint:** try something, see what fails, define something to make that work."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "x = ModInt{12}(9)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "y = ModInt{15}(13)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "# two method definitions here..."
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "@assert x + y == ModInt{60}(22)\n",
    "@assert x * y == ModInt{60}(57)"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Julia 1.1.0-DEV",
   "language": "julia",
   "name": "julia-1.1"
  },
  "language": "Julia",
  "language_info": {
   "file_extension": ".jl",
   "mimetype": "application/julia",
   "name": "julia",
   "version": "1.1.0"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}
